export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}
// 方法1: 递归解法 - 使用上下界
function isValidBST(root: TreeNode | null): boolean {
    return validate(root, -Infinity, Infinity);
}

function validate(node: TreeNode | null, min: number, max: number): boolean {
    // 空节点是有效的BST
    if (node === null) return true;

    // 检查当前节点值是否在允许范围内
    if (node.val <= min || node.val >= max) return false;

    // 递归检查左右子树
    // 左子树的所有节点值必须小于当前节点值
    // 右子树的所有节点值必须大于当前节点值
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}
// 方法2: 中序遍历解法
function isValidBST2(root: TreeNode | null): boolean {
    let prev: number | null = null;

    function inOrderTraversal(node: TreeNode | null): boolean {
        if (node === null) return true;

        // 遍历左子树
        if (!inOrderTraversal(node.left)) return false;

        // 检查当前节点：中序遍历BST应该得到升序序列
        if (prev !== null && node.val <= prev) return false;
        prev = node.val;

        // 遍历右子树
        return inOrderTraversal(node.right);
    }

    return inOrderTraversal(root);
}